#include "myGraph.h"
#include <iostream>
#include <sstream>
#include <string>
#include <queue>
#include<list>

using namespace std;

EdgeNode::EdgeNode(){
	dest = 0; link = NULL;
}
EdgeNode::EdgeNode(int dest1, EdgeNode* link1){
	dest = dest1; link = link1;
}
EdgeNode::~EdgeNode(){
	
}
int EdgeNode::getDest(){
	return dest;
}
EdgeNode* EdgeNode::getNext(){
	return link;
}
void EdgeNode::setDest(int dest1){
	dest = dest1;
}
void EdgeNode::setNext(EdgeNode* link1){
	link = link1;
}
VertexNode::VertexNode(){
	data = 0; firstEdge = NULL;
}
VertexNode::VertexNode(char data1, EdgeNode* firstEdge1){
	data = data1; firstEdge = firstEdge1;
}
VertexNode::~VertexNode(){
	/*data = 0; EdgeNode* current = firstEdge;
	while (current != NULL) {
		EdgeNode* temp = current; current = current->getNext(); 
		delete current;
	}*/
}
char VertexNode::getData(){
	return data;
}
EdgeNode* VertexNode::getFirstEdge(){
	return firstEdge;
}
void VertexNode::setData(char data1){
	data = data1;
}
void VertexNode::setFirstEdge(EdgeNode* firstEdge1){
	firstEdge = firstEdge1;
}
MyGraph::MyGraph(){
	nodeNum = 0; edgeNum = 0; VexList = NULL;
}
MyGraph::MyGraph(int nodeNum1, int edgeNum1, char* nodeList, int* edgeStartList, int* edgeEndList){
	nodeNum = nodeNum1; edgeNum = edgeNum1; VexList = new VertexNode[nodeNum];
	for (int i = 0; i < nodeNum; i++) { VexList[i].setData(nodeList[i]); }
	for (int i=0; i < edgeNum; i++) {
		int from = edgeStartList[i], to = edgeEndList[i];
		EdgeNode* newedge = new EdgeNode(to, VexList[from].getFirstEdge());
		VexList[from].setFirstEdge(newedge);

		EdgeNode* newedge2 = new EdgeNode(from, VexList[to].getFirstEdge());
		VexList[to].setFirstEdge(newedge2);
	}
}
MyGraph::~MyGraph(){
	for (int i = 0; i < nodeNum; i++) {
		VertexNode* vertex = &VexList[i]; delete vertex->getFirstEdge();
	}
	delete[]VexList;
}
int MyGraph::getNodeNum(){
	return nodeNum;
}
int MyGraph::getEdgeNum(){
	return edgeNum;
}
string MyGraph::printGraph(){
	ostringstream oss;
	for (int i = 0; i < nodeNum; i++) {
		
		 oss<< VexList[i].getData()<<":";
		EdgeNode* edge = VexList[i].getFirstEdge();
		while (edge != NULL) {
			oss << " " << VexList[edge->getDest()].getData();
			edge = edge->getNext();
		}
		if (i < nodeNum - 1) { oss << endl; }
	}
	return oss.str();
}
/*int MyGraph::getFirstNeighbor(int v, int* visited) {

}

int MyGraph::getNextNeighbor(int v, int w, int* visited){

}
*/
void MyGraph::DFS(int v, int* visited, string& result){
	visited[v] = 1;
	result += VexList[v].getData();result+=" ";
	EdgeNode* edge = VexList[v].getFirstEdge();
	while (edge != NULL) {
		if (!visited[edge->getDest()]) {
			DFS(edge->getDest(), visited, result);
		}
		edge = edge->getNext();
	}
}

string MyGraph::graph_DFS_Traverse(){
	int* visited = new int[nodeNum]();
	string result;
	DFS(0, visited, result);
	delete[]visited;
	return result;
}

void MyGraph::BFS(int v, int* visited, string& result){
	list<int> queue; visited[v] = 1;
	result += VexList[v].getData(); result += " ";
	queue.push_back(v);
	while (!queue.empty()) {
		int current = queue.front();
		queue.pop_front();
		EdgeNode* edge = VexList[current].getFirstEdge();
		while (edge != NULL) {
			if (!visited[edge->getDest()]) {
				visited[edge->getDest()] = 1;
				result += VexList[edge->getDest()].getData();
				result += " ";
				queue.push_back(edge->getDest());
			}
			edge = edge->getNext();
		}
	}
}

string MyGraph::graph_BFS_Traverse(){
	int* visited = new int[nodeNum]();
	string result;
	BFS(0, visited, result);
	delete[]visited;
	return result;
}

/**/